/**
 * 二分查找函数--迭代实现
 * @param {Array} arr - 已排序的数组，必须是升序
 * @param {number} target - 要查找的目标值
 * @returns {number} - 返回目标值在数组中的索引，如果未找到则返回 -1
 */
function BinarySearch(arr, target) {

    /*
    这里可以加一些空数组判断
    * */

    //1.初始化左右指针
    let left=0;
    let right=arr.length-1;
    let mid=0;
    //2.循环
    while(left<=right){
        //计算中间位置
        mid=Math.floor((left+right)/2)
        if(arr[mid]===target){
            return mid
        }
        //小于目标值，目标值在mid右边
        else if(arr[mid]<target){
            left = mid+1
        }
        //大于目标值，目标值在mid左边
        else{
            right=mid-1
        }
    }
    //没有找到，返回-1
    return -1
}

/**
 * 二分查找函数--递归实现
 * @param {Array} arr - 有序数组
 * @param {number} target - 要查找的目标值
 * @param {number} [left=0] - 当前查找范围的左边界，默认为0
 * @param {number} [right=arr.length-1] - 当前查找范围的右边界，默认为数组最后一个元素的索引
 */
function BinarySearch2(arr, target, left = 0, right = arr.length - 1) {

    if(arr.length===0){
        return -1
    }
    let mid=Math.floor((left+right)/2)
    if(left>right){
        return -1
    }
    //1.相等情况
    if(arr[mid]===target){
        return mid
    }
    //2.小于目标值，在右边
    else if(arr[mid]<target){
        return BinarySearch2(arr,target,mid+1,right)
    }
    //3.大于目标值，在左边
    else{
        return BinarySearch2(arr,target,left,mid-1)
    }

}
//准备测试数据
let arr=[]
for(let i=0;i<1000;i++){
    arr.push(i)
}
let target=Math.floor(Math.random()*1000)
console.log(BinarySearch2(arr,target));
// console.log(BinarySearch(arr,target));
